package leetcode_800;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *@author 周杨
 *AsteroidCollision_735 用数组模拟行星碰撞 正负表示行星行走的方向
 *describe:用栈即可 注意边界情况 AC 40%
 *2018年10月14日 下午8:02:57
 */
public class AsteroidCollision_735 {
	public int[] asteroidCollision(int[] asteroids) {
		//结果只有两种
		//----+++ 或者 ---- 或者 ++++ 因为从左往右遍历 那么只考虑正数退栈
        Stack<Integer> stack=new Stack<Integer>();//栈内只保存正数
        List<Integer> val=new ArrayList<Integer>();//记录负数
        for(int i:asteroids) {
        	if(i>=0) {
        		stack.push(i);
        	}
        	else {
        		boolean flag=false;//判断消失掉没有
        		while(!stack.isEmpty()&&-i>=stack.peek()){
        			if(-i==stack.peek()) {//消失掉
        				stack.pop();
        				flag=true;
        				break;
        			}
        			stack.pop();//退栈 试下后面的小行星能否完成碰撞
        		}
        		if(stack.isEmpty()&&!flag) {//全部碰撞完了
        			val.add(i);
        		}
        	}
        }
        int []res=new int[val.size()+stack.size()];
        int i=0;
        for(int v:val) {
        	res[i++]=v;
        }
        for(int v:stack)
        	res[i++]=v;
        return res;
    }
}
